package entity

import "cmp"

/*
BstSearch
线段树（Segment Tree）：一种基于分治思想的二叉树，用于在区间上进行信息统计 对应区间[left right]

每一个叶子节点表示了一个单位区间（长度为1），叶子节点对应区间上 left= right
每一个非叶子节点[left right]的左子节点表示的区间都为 [left (left+right)/2]

	右子节点表示的区间都为 [ (left+right)/2+1,right]

线段树是一棵平衡二叉树，树上的每个节点维护一个区间。根节点维护的是整个区间，每个节点维护的是父亲节点的区间二等分之后的其中一个子区间
当有n 个元素时对区间的操作（单点更新、区间更新、区间查询等）可以在𝑂(log2 n) 的时间复杂度内完成。

特点

根据上述描述，我们可以总结一下线段树的特点：

	线段树的每个节点都代表一个区间。
	线段树具有唯一的根节点，代表的区间是整个统计范围，
	线段树的每个叶子节点都代表一个长度为1 的单位区间
*/

/*
由于线段树近乎是完全二叉树，所以很适合用「顺序存储结构」来实现。
如果某二叉树节点（非叶子节点）的下标为i ，其左孩子节点下标为 2*i+1 ,右孩子节点下标为 2×i+2。
如果某二叉树节点（非根节点）的下标为 i ,那么其父节点下标为(i−1)//2

在理想情况下 线段树是一棵满二叉,2×n 的数组
一般情况下，有些区间元素需要开辟新的一层来存储元素 线段树的深度为⌈log2 N⌉ 最坏情况下叶子节点（包括无用的节点）的数量为 2 ^ (log2 n)，总节点 为2 ^ (log2 n)+1)  近似4n

*/

/*
SegmentBuild
如果是叶子节点（eft==right），则节点的值就是对应位置的元素值。
如果是非叶子节点，则递归创建左子树和右子树。
节点的区间值（区间和、区间最大值、区间最小值）等于该节点左右子节点元素值的对应计算结果。
*/

type SegmentNode[T cmp.Ordered] struct {
	Data        T
	Left, Right int
	LazyTag     byte
}

type SegmentTree[T cmp.Ordered] struct {
	Tree   []SegmentNode[T]
	Nums   []T
	Handle func(left T, right T) T //指的是线段树区间合并的聚合方法
}

// SegmentBuild 构建线段树，节点的存储下标为 index，节点的区间为 [left, right]
func (n *SegmentTree[T]) SegmentBuild(index, left, right int) {
	n.Tree[index].Left = left
	n.Tree[index].Right = right
	if left == right {
		n.Tree[index].Data = n.Nums[index]
	}
	mid := left + (right - left)              // 2            // 左右节点划分点
	left_index := index*2 + 1                 // 左子节点的存储下标
	right_index := index*2 + 2                // 右子节点的存储下标
	n.SegmentBuild(left_index, left, mid)     // 递归创建左子树
	n.SegmentBuild(right_index, mid+1, right) // 递归创建右子树
	n.SegmentPushUp(index)                    // 向上更新节点的区间值
}

func (n *SegmentTree[T]) SegmentPushUp(index int) {
	left_index := index*2 + 1  // 左子节点的存储下标
	right_index := index*2 + 2 // 右子节点的存储下标
	n.Tree[index].Data = n.Handle(n.Tree[left_index].Data, n.Tree[right_index].Data)
}
